import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: wenjingyuan
 * @Date: 2022/01/06/18:35
 * @Description:基于int的最小堆实现
 * 下标从0开始
 */
public class MinHeap {
   private List<Integer> data;
   public MinHeap(){
      this(10);
   }
   public MinHeap(int initcap){
      data=new ArrayList<>(initcap);
   }

   /**
    * 求得下标为k节点的父节点
    * @param k
    * @return
    */
   public int parent(int k){
     return (k-1)>>1;
   }

   /**
    * 根据k节点求出此时左孩子的节点
    * @param k
    * @return
    */
   public int leftChild(int k){
      return (k<<1)+1;
   }

   /**
    * 根据k节点求出此时右孩子的节点
    * @param k
    * @return
    */
   public int rightChild(int k){
      return (k<<1)+2;
   }

   /**
    * 将数组中的元素最小堆化
    * @param arr
    */
   public MinHeap(int[] arr){
      //先将arr所有元素拷贝到data中
      data=new ArrayList<>(arr.length);
      for(int i:arr){
         data.add(i);
      }
     //从第一个非叶子节点开始判断，开始元素下沉
      for (int i = parent(data.size())-1; i >=0 ; i--) {
         siftDown(i);
      }
   }
   /**
    * 取出最小元素
    * @return
    */
   public int extractMin(){
      int min=data.get(0);
      data.set(0,data.get(data.size()-1));
      data.remove(data.size()-1);
      siftDown(0);
      return min;
   }

   /**
    * 下沉操作
    * @param i
    */
   private void siftDown(int i) {
      while(leftChild(i)< data.size()){
         int j=leftChild(i);
         if(j+1< data.size() && data.get(j+1)<data.get(j)){
            j=j+1;
         }
         swap(j,i);
         i=j;
      }
   }

   /**
    * 在数组末尾添加元素，使其仍然构成最小堆
    * @param value
    */
   public void add(int value){
      //在数组末尾添加元素
      data.add(value);
      //上浮操作
      siftUp(data.size()-1);
   }

   /**
    * 元素的上浮操作
    * @param i
    */
   private void siftUp(int i) {
      //当i=0或者父节点的元素值小于孩子节点的元素值不进行
      while(i>0 && data.get(i)<=data.get(parent(i))){
         swap(i,parent(i));
         i=parent(i);
      }

   }
   //交换两个元素对应的值
   private void swap(int i, int parent) {
      int temp=data.get(i);
      data.set(i, data.get(parent));
      data.set(parent,temp);
   }

   @Override
   public String toString() {
      return data.toString();
   }

   //添加操作实验
   public static void main(String[] args) {
      int [] test={33,41,49,31,45,28,20,19,12,18,25,32,52};
      MinHeap heap=new MinHeap(test.length);
      for (int i = 0; i < test.length; i++) {
         heap.add(test[i]);
      }
      System.out.println(heap);
   }
   //取出测试
//   public static void main(String[] args) {
//      int [] test ={33,41,49,31,45,28,20,19,12,18,25,32,52};
//      MinHeap heap=new MinHeap(test.length);
//      for (int i = 0; i < test.length; i++) {
//         heap.add(test[i]);
//      }
//      for (int i = 0; i < test.length; i++) {
//         test[i]=heap.extractMin();
//      }
//      System.out.println(Arrays.toString(test));
//   }
   //堆化测试
//   public static void main(String[] args) {
//      int [] test={33,41,49,31,45,28,20,19,12,18,25,32,52};
//      MinHeap heap=new MinHeap(test);
//      for (int i = 0; i < test.length; i++) {
//         test[i]=heap.extractMin();
//      }
//      System.out.println(Arrays.toString(test));
//   }
}
